The principal prior art method for performing a real-time discrete Fourier transform (DFT) is the chirp-Z transform implemented, for example, as described in U.S. Pat. No. 3,900,721, entitled "Serial-Access Linear Transform," which issued on Aug. 19, 1975, to J. M. Speiser et al. This prior art implementation uses a complex point-by-point premultiplication, followed by a complex transversal filter, followed by a complex point-by-point postmultiplication. The two sets of multiplications, especially the postmultiplication, contribute to the limitations in accuracy and dynamic range of that specific implementation. This prior art implementation is shown in FIG. 1.
Another method for performing the discrete Fourier transform via convolution using a transversal filter is by using the prime transform algorithm. This method is similar to the method using the chirp-Z transform except that the point-by-point multiplications are replaced by permutations. The accuracy of prime transform implementations has been limited by permuter errors.
Errors in the point-by-point pulse multiplication, using the chirp-Z algorithm, or errors in permutation, using the prime transform, are particularly troublesome, since no subsequent convolution is performed to average out the effect of such errors.
Performing the discrete Fourier transform using the prime transform is described in U.S. Pat. No. 4,068,311, entitled "DISCRETE TRANSFORM SYSTEMS USING PERMUTER MEMORIES," which issued on Jan. 10, 1978, to H. J. Whitehouse et al.